package acwing._1_1AlgorithmBasic;

/**
 * @Project : ProgrammingExercises
 * @Package : ACWing.Learning.AlgorithmTemplate
 * @File : _2_5DisjointSetUnion.java
 * @Author : WangRuoyu
 * @Date 2023/3/12 10:46
 */

public class _2_5DisjointSetUnion {
    private int[] father; // 存储每个点的父亲节点
    private int[] size; // 存储每个集合中点的个数

    public _2_5DisjointSetUnion(int n) {
        father = new int[n + 1];
        size = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }

    public int findDSU(int x) {// 寻找x的集合号，即x的祖宗节点，同时对于路径做优化；
        if (father[x] != x) father[x] = findDSU(father[x]);
        return father[x];
    }

    public void mergeDSU(int a, int b) {
        int aFather = findDSU(a);
        int bFather = findDSU(b);
        if (aFather == bFather) {
            return;
        }
        father[aFather] = bFather;
        size[bFather] += size[aFather];
    }

    public boolean queryDSU(int a, int b) {
        if (a == b) {
            return true;
        }
        if (findDSU(a) == findDSU(b)) {
            return true;
        }
        return false;
    }

    public int querySize(int a) {
        return size[findDSU(a)];
    }
}
